package com.sicheng.lc.周赛.分类.图论.拓扑排序;

import java.util.ArrayDeque;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/31 13:01
 */
public class 图中的最长环 {
    //https://leetcode.cn/problems/longest-cycle-in-a-graph/
    public int longestCycle(int[] edges) {
        // 大致思路 使用拓扑排消除 环的枝叶, 剩下的就是环
        // 找每个环的入口 把环逻辑消掉,统计每个环的长度就好了
        int[] degree = new int[edges.length];
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int e : edges) {
            if (e >= 0)
                degree[e]++;
        }

        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                deque.push(i);
            }
        }

        int cnt = 0;
        while (!deque.isEmpty()) {
            int x = deque.pop();
            cnt++;
            if (edges[x] >= 0) {
                degree[edges[x]]--;
                if (degree[edges[x]] == 0)
                    deque.push(edges[x]);
            }
        }
        if (cnt == edges.length)
            return -1;

        int max = -1;
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] > 0) {
                degree[i] = -1;
                int d = 1;
                for (int j = edges[i]; j >= 0 && degree[j] > 0; j = edges[j]) {
                    d++;
                    degree[j] = -1;
                }
                max = Math.max(max, d);
            }
        }

        return max;
    }
}
